package study.datastructure.link.leetcode;/**
 * @program: datastructure
 * @author: lcy
 * @create: 2024-10-18 19:36
 */

/**
 2024/10/18,
 */

/**
 *给你一个单链表的头节点 head ，请你判断该链表是否为
 * 回文链表
 * 。如果是，返回 true ；否则，返回 false 。
 */
public class Client234 {
    // 1 2 2 1
    public boolean isPalindrome(ListNode head) {

        ListNode newHead=getMiddle(head);
        System.out.println(newHead);

        newHead=reverse(newHead);
        System.out.println(newHead);

        while (newHead!=null) {
            if (newHead.val!= head.val){
                return false;
            }
            newHead=newHead.next;
            head=head.next;
        }

        return true;
    }

    private ListNode getMiddle(ListNode head) {
        ListNode p1=head;
        ListNode p2=head;

        while (p2!=null&&p2.next!=null){
            p1=p1.next;
            p2=p2.next;
            p2=p2.next;
        }
        return p1;
    }

    private ListNode reverse(ListNode newHead) { //反转后面 不需要考虑奇偶

        ListNode n=null;

        while (newHead!=null){
            ListNode next = newHead.next;
            newHead.next=n;
            n=newHead;
            newHead=next;
        }
        return n;
    }
    //      1 2 3 3 2 1 null
    //            p1
    //                  p2
    // 3 2 1  3 2 1

    //      1 2 3 2 1 null
    //          p1
    //              p2
    //      1 2 3  3 2 1
 public boolean isPalindrome1(ListNode head) {
    //快慢指针 找中点
     ListNode p1= head;
     ListNode p2= head;
     ListNode n=null; //新链表
     ListNode o1=head; //旧链表

     while (p2!=null&&p2.next!=null){ //边找出中点 边反转 截至条件是中点 如果是偶的正好 前后想等 如果是奇的前小于后一个
         p1=p1.next;
         p2=p2.next;
         p2=p2.next;

         o1.next=n;
         n=o1;
         o1=p1;

     }
     System.out.println("n = " + n);
    if (p2!=null){
        p1=p1.next;
    }
     System.out.println("p1 = " + p1);
     while (n!=null){
         if (n.val!=p1.val){
             return false;
         }
         n=n.next;
         p1=p1.next;
     }
     /*ListNode newHead= p1;
        System.out.println(newHead);
        //反转链表
     ListNode newHead1 = newHead;

     ListNode n=null;

     while (newHead1 !=null){
         ListNode next = newHead1.next;
         newHead1.next=n;
         n= newHead1;
         newHead1 =next;
     }
     newHead= n;
        System.out.println(newHead);
        //比较
        while (newHead!=null) {
            if (newHead.val!= head.val){
                return false;
            }
            newHead=newHead.next;
            head=head.next;
        }
*/
        return true;
    }

    public static void main(String[] args) {
        //ListNode t6=new ListNode(1,null);
        ListNode t5=new ListNode(1,null);
        ListNode t4=new ListNode(2,t5);
        ListNode t3=new ListNode(4,t4);
        ListNode t2=new ListNode(2,t3);
        ListNode t1=new ListNode(1,t2);
        Client234 test=new Client234();
        if (test.isPalindrome1(t1)){
            System.out.println("测试成功");
        }else {
            System.out.println("测试失败");
        }
    }
}
